package Triangulation;

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Set;
import java.util.Vector;

import datatypes.Edge;
import datatypes.IndexedFaceSet;
import datatypes.Vertex;
import static controller.DraftingHint.*;

/**
 * Optimal triangulation of a simple (convex) polygon.
 * 
 * @author Andreas
 * 
 */
public class PolygonTriangulator implements EdgeGenerator
{

	/**
	 * Represents a solution for a subproblem in the dynamic programming
	 * algorithm. A solution is the optimal triangulation below the diagonal
	 * between points[i] and points[j].
	 * 
	 * @author Andreas
	 * 
	 */
	class Solution
	{
		Solution(int i, int j)
		{
			this.i = i;
			this.j = j;
		}

		boolean solved = false;
		boolean added = false;
		double cost = 999999999999.0;
		int k = -1;
		int i, j;

		/**
		 * Retrieves the triangulation of this solution.
		 * 
		 * @param points
		 *            Input points.
		 * @param tris
		 *            Output edge list.
		 * @param s
		 *            array of all solutions.
		 */
		void getTriangulation(Vertex[] points, Vector<Edge> tris, Solution[][] s)
		{
			if (added || k == -1)
				return;
			added = true;
			tris.add(new Edge(points[i], points[j], LMT_HOLE));
			tris.add(new Edge(points[i], points[k], LMT_HOLE));
			tris.add(new Edge(points[j], points[k], LMT_HOLE));
			if (j - k > 1)
				s[k][j].getTriangulation(points, tris, s);
			if (k - i > 1)
				s[i][k].getTriangulation(points, tris, s);
		}
	}

	/**
	 * Solves the subproblem s(i,j) recursively. The solution of a subproblem is
	 * a Triangle (i,j,k), which minimizes w(i,j,k) + w(s(i,k)) + w(s(k,j)).
	 */
	public void solveSubProblem(int i, int j, Solution[][] s, Vertex[] points, Vector<Edge> polyEdges)
	{
		if (s[i][j].solved)
			return;
		if (i == j || i == j - 1)
		{
			s[i][j].solved = true;
			s[i][j].cost = 0;
			return;
		}
		
		//test whether edge (i,j) is inside the polygon (for non-convex polygons)
		//if not, mark problem as solved, bust cost remains at 999999999
		if (! (i == 0 && j == points.length-1)
			&& !isEdgeInPolygon(points[i], points[j], polyEdges))
		{
			s[i][j].solved = true;
			return;
		}

		s[i][j].solved = true;
		// System.out.println("Solving " + Integer.toString(i) + " " +
		// Integer.toString(j));
		for (int k = i + 1; k < j; k++)
		{
			solveSubProblem(i, k, s, points, polyEdges);
			solveSubProblem(k, j, s, points, polyEdges);
			double cost = s[i][k].cost + s[k][j].cost
					+ getTriangleQuality(points, i, j, k);
			if (cost < s[i][j].cost)
			{
				s[i][j].cost = cost;
				s[i][j].k = k;
			}
		}
		// System.out.println("Solved " + Integer.toString(i) + " " +
		// Integer.toString(j) + " = " + Integer.toString(s[i][j].k));
		return;
	}
	
	private boolean isEdgeInPolygon(Vertex p0, Vertex p1, Vector<Edge> polyEdges)
	{
		Vertex diff = p1.getMinus(p0);
		Vertex offset = diff.multiplyWithScalar(0.01);
		Edge pRay = new Edge(p0.getPlus(offset), p1.getMinus(offset));
		for (Edge e : polyEdges)
		{
			if (pRay.intersects(e, Double.MIN_VALUE))
				return false;
		}
		//no intersection with the polygon
		//now test whether the middle of the edge is inside the polygon, to ensure that the edge is not completely outside
		Vertex middle = p0.getPlus(diff.multiplyWithScalar(0.5));
		pRay = new Edge(middle, new Vertex(middle.getX(), 10000000.0));
		int numIntersections = 0;
		for (Edge e : polyEdges)
		{
			if (pRay.intersects(e, Double.MIN_VALUE))
				numIntersections++;
		}
		
		return ((numIntersections % 2) == 1);	//point is inside polygon if number of intersections is not even
	}

	/**
	 * @remarks: This triangulates a polygon, not a set of points. The order of
	 *           the points matters!
	 */
	@Override
	public Vector<Edge> processVertices(Vertex[] points)
	{
		int n = points.length;
		Vector<Edge> tris = new Vector<Edge>();
		if (n == 0)
			return tris;
		Solution[][] s = new Solution[points.length][points.length];
		for (int i = 0; i < points.length; i++)
			for (int j = 0; j < points.length; j++)
				s[i][j] = new Solution(i, j);
		
		Vector<Edge> polyEdges = new Vector<Edge>();	//for point-in-polygon raycasts
		for (int i = 1; i < points.length; i++) polyEdges.add(new Edge(points[i-1], points[i]));
		polyEdges.add(new Edge(points[points.length-1], points[0]));	
		
		solveSubProblem(0, n - 1, s, points, polyEdges);
		
		s[0][n - 1].getTriangulation(points, tris, s);

		return tris;
	}

	double getTriangleQuality(Vertex[] points, int a, int b, int c)
	{
		return points[a].dist(points[b]) + points[a].dist(points[c])
				+ points[b].dist(points[c]);
	}

	@Override
	public String getName()
	{
		return "Simple Polygon";
	}
	
	public Vector<Vertex> cycleSearch(Vertex v, IndexedFaceSet lmt, Set<Vertex> polyVertices, Vector<Vertex> path)
	{
		if (v.userFlags == 1)
		{
			//test whether the cycle contains all polygon Vertices
			for (Vertex vc : polyVertices)
			{
				if (!path.contains(vc)) return null;
			}
			return path;	//correct cycle found
		}
		else
		{		
			v.userFlags = 1;
			Set<Edge> edges = lmt.getEdgesInContainingVertex(v);
			Vector<Vertex> pathCopy = new Vector<Vertex>();
			for (Edge e : edges)
			{
				Vertex n = e.getOtherVertex(v);
				if (!polyVertices.contains(n)) continue;
				pathCopy.clear();
				if (path != null) pathCopy.addAll(path);
				pathCopy.add(v);
				Vector<Vertex> cycle = cycleSearch(e.getOtherVertex(v), lmt, polyVertices, pathCopy);
				if (cycle != null) return cycle;
			}
			v.userFlags = 2;
		}
		return null;
	}

	public void triangulateLMTHoles(IndexedFaceSet lmt)
	{
		Iterator<Edge> it = lmt.getCandidateEdges().iterator();
		while (it.hasNext())
		{
			Edge edge = it.next();
			if (edge.userFlags == 1) continue;	//already processed - skip
			
			//1. find a set of vertices forming a polygon using the candidate edges
			
			LinkedList<Edge> edgeQueue = new LinkedList<Edge>();
			edgeQueue.add(edge);
			
			Set<Vertex> polyVertices = new HashSet<Vertex>();
			
			while (!edgeQueue.isEmpty())
			{
				Edge head = edgeQueue.pop();
				head.userFlags = 1;
				
				for (Edge edge2 : lmt.getCandidateEdges())
				{
					if (edge2.userFlags == 1) continue;
					if (head.getVertex1() != edge2.getVertex1() && head.getVertex1() != edge2.getVertex2() && head.getVertex2() != edge2.getVertex1() && head.getVertex2() != edge2.getVertex2()
						&& head.intersects(edge2, Double.MIN_VALUE)) {
						edge2.userFlags = 1;
						edgeQueue.add(edge2);
					}
				}
				polyVertices.add(head.getVertex1());
				polyVertices.add(head.getVertex2());
				
			}
			
			if (polyVertices.isEmpty()) continue;
			
			System.out.println("Found LMT hole with " + polyVertices.size() + " vertices");
			
			//2. we know the vertices, but not the correct order
			//in the graph containing the vertices + edges, we perform a depth-first search to find all cycles
			//the cycle that contains all vertices is the correct polygon
			Vector<Vertex> polygon = cycleSearch(polyVertices.iterator().next(), lmt, polyVertices, null);
			
			//cleanup
			for (Vertex v : polyVertices) v.userFlags = 0;
			
			if (polygon == null)
			{
				System.out.println("Warning: Invalid hole polygon!");
				continue;		//should never happen, but never say never				
			}

			System.out.println("Filling LMT hole with " + polygon.size() + " vertices");
            Vertex[] aPolygon = new Vertex[polygon.size()]; 
            polygon.toArray(aPolygon); 			
            Vector<Edge> polyEdges = processVertices(aPolygon);
            for (Edge e: polyEdges) lmt.edgesIn.add(e);
			
		}
	}

}
